/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package huffmantree;

import java.util.*;
/**
 *
 * @author Administrator
 */
public class HuffmanTree {

    public LinkedList<BinaryTree<StringDetails>> list = new LinkedList();
    public String abc = "ABCDEFGHIJKLMNOPQRSTUVWXYZ ";
    public int[] frequency = new int[abc.length()];
    
    public void Analize(String cadena){

        cadena = cadena.toUpperCase();
        initFreq();
        for (int i = 0; i < cadena.length(); i++)
            frequency[abc.indexOf(cadena.charAt(i))]++;
        makeTrees();
        makeHauffmanTree();
        makeCodes();    
    }

    public void initFreq(){
        for (int i = 0; i < frequency.length; i++)
            frequency[i] = 0;
    }

    public void makeTrees(){
        
        for (int i = 0; i < frequency.length; i++)
            if (frequency[i] > 0){
                StringDetails temp = new StringDetails();
                temp.setFrequency(frequency[i]);
                temp.setString(abc.substring(i,i+1));
                BinaryTree<StringDetails> treetemp = new BinaryTree();
                treetemp.setValue(temp);
                insertTree(treetemp);
            }
    }
    
    public void insertTree(BinaryTree<StringDetails> t){
        boolean found = false;
        int count = 0;

        if (list.size() == 0)
            list.add(0, t);
        else
            while(!found){
                if (count == list.size()){
                    list.add(count, t);
                    found = true;
                }
                else
                    if (t.getValue().getFrequency() > list.get(count).getValue().getFrequency())
                        count++;
                    else{
                        list.add(count, t);
                        found = true;
                    }
            }
    }

    public void makeHauffmanTree(){
        
        String str;
        int freq;

        while(list.size() > 1){
            str = list.get(0).getValue().getString() + list.get(1).getValue().getString();
            freq = list.get(0).getValue().getFrequency() + list.get(1).getValue().getFrequency();
            BinaryTree<StringDetails> temp = new BinaryTree();
            temp.setValue(new StringDetails(str,freq));
            temp.setLeft(list.removeFirst());
            temp.setRight(list.removeFirst());
            list.addFirst(temp);
        }          
    }
    
    public void makeCodes(){
        String right = "0", left = "1", codetmp;
        StringDetails stemp = list.getFirst().getValue();

        for (int i = 0; i < stemp.getString().length(); i++){
            BinaryTree<StringDetails> temp = list.getFirst();
            codetmp = "";
            while(!((temp.getLeft() == null) && (temp.getRight() == null))){
                if (temp.getLeft().getValue().getString().contains(stemp.getString().substring(i, i+1))){
                    temp = temp.getLeft();
                    codetmp = codetmp + left;
                }
                else{
                    temp = temp.getRight();
                    codetmp = codetmp + right;
                }   
            }
            temp.getValue().setCode(codetmp);
        }
    }

    public String toString(){

        
        String s = "Character    Frequency    Code";
        StringDetails stemp = list.getFirst().getValue();
        String[] megastring = new String[stemp.getString().length()+1];
        megastring[0] = s;

        for (int i = 0; i < stemp.getString().length(); i++){
            BinaryTree<StringDetails> temp = list.getFirst();
            while(!((temp.getLeft() == null) && (temp.getRight() == null))){
                if (temp.getLeft().getValue().getString().contains(stemp.getString().substring(i, i+1)))
                    temp = temp.getLeft();
                else
                    temp = temp.getRight();
            }
            megastring[i+1] = ("" + temp.getValue().getString() + "            " + temp.getValue().getFrequency() + "            " + temp.getValue().getCode());
            //s = (s + temp.getValue().getString() + "            " + temp.getValue().getFrequency() + "            " + temp.getValue().getCode()) + "\n";
        }

        for (int i = 1; i < megastring.length - 1; i++)
            for(int j = i; j < megastring.length; j++){
                if(megastring[i].charAt(0) > megastring[j].charAt(0)){
                    s = megastring[i];
                    megastring[i] = megastring [j];
                    megastring[j] = s;
                }
            }

        s = "";
        for (int i = 0; i < megastring.length; i++)
            s = s + megastring[i] + "\n";

        return(s);
    }
}
